网络流总结 做题记录

网络流 24 题

Blog

1.二分图

二分图对偶定理

二分图最大权匹配 == 二分图最小点权覆盖 == w|∑w| - 二分图最大点权独立集

1.最小点权覆盖

若一个点集 PVP \subseteq V , 使得: (u,v)E\forall(u,v) \in E , (uP)(vP)(u \in P) \lor (v \in P) ,那么 PP 便是原图的一个点覆盖。

对于所有满足条件的 PP , uPwu\sum_{u \in P} w_u 的最小值即为最小点权覆盖。


  • 将二分图的两部分分别与源点/汇点连容量为点权的边

  • 二分图内部的边容量设为 ++\infty

最后图的最小割即为原二分图的最小点权覆盖。


考虑这样做的正确性:

二分图的点覆盖中每条边都至少被一个点覆盖,所以没有源点到汇点的路径,是新图的割。

新图的割的边集只可能包含源点与汇点为顶点的边(内部的边容量为 ++\infty),那么割掉一条边对应选出这个点。

2.最大点权独立集

若一个点集 PVP \subseteq V , 使得: (u,v)E\forall(u,v) \in E , (uP)(vP)(u \notin P) \lor (v \notin P) , 那么 PP 便是原图的一个点独立集。

对于所有满足条件的 PP , uPwu\sum_{u \in P} w_u 的最大值即为最大点权独立集。


由对偶定理和 1. 易得解法,不再赘述。


eg.\text{eg.} 2020.12.30、2020.12.31 题目

2.最大权闭合子图

对于原图 G=(V,E)G=(V,E) 的一个子图 G=(V,E={(u,v)(u,v)EuVvV})G'=(V',E'=\{(u,v)| (u,v) \in E \land u \in V' \land v \in V'\})

若: uV,(u,v)E\forall u \in V', (u,v) \in E ,有 vVv \in V',那么 GG' 为原图的闭合子图。

对于所有满足条件的 GG'uVwu\sum_{u \in V'} w_u 的最大值即为原图的最大权闭合子图。


  • 对于原图中点权为正的点 uu,连接 (s,u)(s,u) , 容量为 wiw_i

  • 对于原图中点权为负的点 vv,连接 (v,t)(v,t) ,容量为 wi-w_i

  • 对于原图中的边,连接 (u,v)(u,v) , 容量为 ++\infty

答案即为所有正权点的权值之和减去新图的最小割。


咕咕咕...


eg.\text{eg.} 2020.12.26 题目

3.最大密度子图

对于原图 G=(V,E)G=(V,E) 的一个子图 G=(V,E={(u,v)(u,v)EuVvV})G'=(V',E'=\{(u,v)| (u,v) \in E \land u \in V' \land v \in V'\})

该子图的密度为: D=EVD'=\frac{|E'|}{|V'|}

对于所有子图 GG' ,密度最大的子图即为原图的最大密度子图。



4.对偶图

5.混合图欧拉回路

eg.\text{eg.} [POI2010]MOS-Bridges

6.集合划分问题

将元素划分为两个集合 A,BA,B , 满足 AB=UA \cup B = UAB=A \cap B = \varnothing

ii 件物品被选入 AA 集合花费 aia_i 的收益,选入 BB 集合花费 bib_i 的收益。

ui,viu_i,v_i 不在同一集合会有 cic_i 的收益。

若集合 SiS_i 中所有元素在同一集合有 did_i 的收益。

求划分的最大收益。(收益可能为负数,可以理解为代价)


  • 从源点/汇点向每个点连容量为 ai,bi|a_i|,|b_i| 的边。

  • ui,viu_i,v_i 之间连容量为 ci|c_i| 的边。

  • 新建一个限制点 pp ,

  1. 属于 AA 集合则源点向 pp 连容量为 di|d_i| 的边,ppSS 内所有点连容量为 ++\infty 的边。

  2. 属于 BB 集合则 pp 向汇点连容量为 di|d_i| 的边,SS 内所有点向 pp 连容量为 ++\infty 的边。

所有的正收益 - 图的最小割 即为最大收益。


点直接连向源汇点的边最多会且只会被割一条。若 (S,u)(S,u) 被割则表示选入 BB 集合,反之若 (u,T)(u,T) 被割则表示选入 AA 集合。

(u,v)(u,v) 被割则表示不要 cic_i 的收益。

pp 要么被割源汇点的边,表示不要 did_i 的收益,要么它连向的所有点到源汇的边被割,满足要求。

可以看出,图的割便是一个选择方案,选择方案也对应一个割。求出最小割即可。


eg.\text{eg.} BZOJ4177 Mike的农场

2020.12.28 题目

7.方格问题

类型一:格子之间有要求

格点之间的要求视作边,若是二分图则是最大点权独立集。

eg.\text{eg.} P2774 方格取数问题    ~~~ P3355 骑士共存问题

类型二:每行、每列、每个格子有要求

对于每行、每列分别建一个点

行与列之间的边对应格子限制,源点与行的边 / 汇点与列的边 对应 行 / 列 的限制。

值得注意的是,这个图也是一个二分图。

eg.\text{eg.} P4311 士兵占领    ~~~ P4194 矩阵

8.时间限制

类型一:分层图

对于每一个时刻建立一层图,耗费的时间可以根据不同层数的图连边来刻画。

这样建立的图往往很大,效率低下,尽量不要使用。

eg.\text{eg.} [CTSC1999]家园 / 星际转移问题    ~~~ P4400 [JSOI2008]Blue Mary的旅行

类型二:最小链覆盖

将两件事情可以连续完成刻画为一条边,图的最小链覆盖可以解决一些安排问题。

连续完成的要求一般与时间有关。

eg.\text{eg.} P4452 [国家集训队]航班安排    ~~~ P5769 [JSOI2016]飞机调度

做题记录

2020.12.18 拆点、最大流

P3153 [CQOI2009]跳舞

二分答案 + 拆点 + 最大流

P3163 [CQOI2014]危桥

最大流


2020.12.19 最大流/最小割

*SP839 Optimal Marks

按位考虑 + 最小割


2020.12.21 上下界网络流

P4311 士兵占领

P4843 清理雪道

UVA1440 Inspection

2020.12.22 上下界网络流

P4194 矩阵


2020.12.23 拆点、最大流

UVA12125 March of the Penguins

拆点

*SP4063 Sell Pigs

最大流建模


2020.12.24 最大流/最小割

*P1344 [USACO4.4]Pollutant Control

特殊处理:

在最小割最小的前提下,让割的边最少。

对每一条 (u,v,c)(u,v,c) 的边变为 (u,v,c×base+1)(u,v,c \times base+1)(base>m)(base > m)

最后 Maxflow/base\text{Maxflow} /base 为最小割, Maxflow%base\text{Maxflow}\%base 为最少边。

*P2057 [SHOI2007]善意的投票 / [JLOI2010]冠军调查

最小割建模

2020.12.25 最大流/最小割

UVA1660 Cable TV Network & SP300 Cable TV Network

最小割建模

*P4662 [BalticOI 2008]黑手党

最小割建模

P3191 [HNOI2007]紧急疏散

最大流建模

P2402 奶牛隐藏

最大流建模


2020.12.26 最大权闭合子图

CF1082G Petya and Graph

P4174 [NOI2006]最大获利

P3410 拍照

*P4177 [CEOI2008]order

注意经典模型的转换。

Solution

P3749 [六省联考2017]寿司餐厅

*CF103E Buying Sets

特殊条件的运用。

P5295 [北京省选集训2019]图的难题

结论题 + 退流

退流似乎用处不大,毕竟建图的时间肯定小于网络流的时间。


*2020.12.28 集合划分问题

P1361 小M的作物

P1935 [国家集训队]圈地计划

P4313 文理分科 & P1646 [国家集训队]happiness

P4210 土地划分


2020.12.28 最小割

P2598 [ZJOI2009]狼和羊的故事

最小割建模

P6094 [JSOI2015]圈地

上一题的加强版

2020.12.29 最小割

*P3227 [HNOI2013]切糕

最小割建模

P3973 [TJOI2015]线性代数

最小割建模

P5934 [清华集训2012]最小生成树

最小割建模

P1791 [国家集训队]人员雇佣


2020.12.30 二分图

*P5771 [JSOI2016]反质数序列

最大权独立集

P2172 [国家集训队]部落战争

最小路径覆盖

P4589 [TJOI2018]智力竞赛

最小路径覆盖

SP741 STEAD - Steady Cow Assignment

二分图匹配

UVA1194 Machine Schedule

最小点权覆盖

2020.12.31 二分图

P6062 [USACO05JAN]Muddy Fields G

最小点覆盖

P2825 [HEOI2016/TJOI2016]游戏

最大匹配


2021.1.4 费用流

P4068 [SDOI2016]数字配对

2020.1.5 费用流

P4209 学习小组

P4400 [JSOI2008]Blue Mary的旅行

2021.1.6 费用流

P2045 方格取数加强版

P2053 [SCOI2007]修车

*P2050 [NOI2012] 美食节

动态加点费用流

2021.1.8 费用流

P2153 [SDOI2009]晨跑

P2517 [HAOI2010]订货

*P4452 [国家集训队]航班安排


todo list

最大闭合子图,最大密度子图,平面图,混合图欧拉回路,集合划分总结

*P4055 [JSOI2009]游戏

匹配 + 博弈论

CF1404E Bricks

P2805 [NOI2009]植物大战僵尸

UVA1389 Hard Life